COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00009 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\parskip 6pt
\rm
\line{\sevenrm a05.tex[162,phy] \today\hfill}

\font\eighttt=amtt8
\scriptfont7=\eighttt

\bigskip
\noindent {\bf Theorem.} If $X↓i≤Y↓i$ for $1≤i≤N$, and we sort $X↓{1:N}$
and~$Y↓{1:N}$, then when we are finished we still have $X↓i≤Y↓i$ for
$1≤i≤N$.

\medskip\noindent
{\bf Proof.} Since the final states of $X$ and $Y$ are independent of which
particular sorting algorithm we use, we pick a sorting algorithm which
leaves $X↓i≤Y↓i$ invariant:

\halign{\qquad{\tt #}\hfil\cr
FOR J:=2 TO N DO\cr
FOR K:=J DOWNTO 2 DO\cr
\qquad BEGIN\cr
\qquad\qquad XMIN:=MIN(X$↓{\tt K-1}$,X$↓{\tt K}$);\cr
\qquad\qquad YMIN:=MIN(Y$↓{\tt K-1}$,Y$↓{\tt K}$);\cr
\qquad\qquad (* XMIN $≤$ YMIN *)\cr
\qquad\qquad XMAX:=MAX(X$↓{\tt K-1}$,X$↓{\tt K}$;\cr
\qquad\qquad YMAX:=MAX(Y$↓{\tt K-1}$,Y$↓{\tt K}$;\cr
\qquad\qquad (* XMAX $≤$ YMAX *)\cr
\qquad\qquad X$↓{\tt K-1}$:=XMIN\cr
\qquad\qquad Y$↓{\tt K-1}$:=YMIN\cr
\qquad\qquad (* X$↓{\tt K-1}≤{\tt Y}↓{\tt K-1}$ *)\cr
\qquad\qquad X$↓{\tt K}$:=XMAX\cr
\qquad\qquad Y$↓{\tt K}$:=YMAX\cr
\qquad\qquad (* X$↓{\tt K}≤{\tt Y}↓{\tt K}$ *)\cr
\qquad END\cr}

$$\vcenter{\halign{\hfil{$#$}\hfil\qquad%
&\hfil{$#$}\hfil\qquad%
&\hfil{$#$}\hfil\qquad%
&\hfil{$#$}\hfil\qquad%
&\hfil{$#$}\hfil\qquad%
&\hfil{$#$}\hfil\qquad%
&\hfil{$#$}\hfil\qquad%
&\hfil{$#$}\hfil\cr
A&&B&&&&C&D\cr
\noalign{\medskip}
Y↓1&Y↓2&Y↓3&Y↓4&Y↓5&Y↓6&Y↓7&+∞\cr
&&&\uparrow&\uparrow&\uparrow&\uparrow\cr
-∞&-∞&X↓3&X↓4&X↓5&X↓6&X↓7&X↓8\cr}}$$

\smallskip
\noindent
{\bf Corollary1.} If $X↓i≤Y↓i$ ($B≤i≤C$) and we sort $Y↓{A:C}$
($A≤C$) and $X↓{B:D}$ ($C≤D$), with $A≤B$, $C≤D$, 
then when we are finished we still have
$X↓i≤Y↓i$ ($B≤i≤C$).

\medskip\noindent
{\bf Proof.} As the diagram above suggsts, provide imaginary variables
$X↓{A:B-1}=-∞$, $Y↓{C+1:D}=+∞$, so $X↓i≤Y↓i$ ($A≤i≤D$). Sorting $X↓{A:D}$
and $Y↓{A:D}$ need not involve the imaginary variables, so it is the same
as sorting $X↓{B:D}$ and $Y↓{A:C}$; apply the theorem to the result.

\medskip\noindent
{\bf Corollary 2.} If the rows of a matrix are ordered, sorting the columns
leaves the rows ordered. Proof is analogous to that of the theorem.

\bigskip
$$\vcenter{\halign{\hfil{$#$}\hfil\quad%
&\hfil{$#$}\hfil\quad%
&\hfil{$#$}\hfil\quad%
&\hfil{$#$}\hfil\quad%
&\hfil{$#$}\hfil\quad%
&\hfil{$#$}\hfil\quad%
&\hfil{$#$}\hfil\quad%
&\hfil{$#$}\hfil\quad%
&\hfil{$#$}\hfil\quad%
&\hfil{$#$}\hfil\quad%
&\hfil{$#$}\hfil\quad%
&\hfil{$#$}\hfil\quad%
&\hfil{$#$}\hfil\cr
-∞&-∞&A↓1&B↓1&C↓1&A↓2&B↓2&C↓2&A↓3&B↓3&C↓3&+∞&+∞\cr
\noalign{\smallskip}
&&\bullet&&\bullet&\bullet&&\bullet&\bullet&&\bullet\cr
\noalign{\smallskip}
\bullet&&\bullet&\bullet&&\bullet&\bullet&&\bullet&\bullet&&\bullet\cr}}$$

\medskip
\noindent
{\bf Corollary 3.} If a 3-ordered array is 2-sorted, it remains 3-ordered.

\medskip\noindent
{\bf Proof.} Append imaginary elements $-∞$ on the left, and $+∞$ on the right,
as needed. Perform the 2-sorting by repeated use of an operation which
simultaneously does 
$\ldots\; CE(M↓{i-3},M↓{i-1})$,
$CE(M↓{i},M↓{i+2})$,
$CE(M↓{i+3},M↓{i+5})$,
$CE(M↓{i+6},M↓{i+8})$,
etc., for $i=1$ or~2.

The operation preserves the three-ordered property, by analogy with the
proof of the theorem. For example, if $M↓i≤M↓{i+3}$ and $M↓{i+2}≤M↓{i+5}$,
then $\min(M↓i,M↓{i+2})≤\min(M↓{i+3},M↓{i+5})$, etc. (More generally, if
a $d↓1$-ordered array is $d↓2$-sorted, it remains $d↓1$-sorted.) An alternate
proof applies Corollary~1.

\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft May 20, 1985 

\bye